package toOffer;

/**
 * @author YuanAo
 * @date 2025/10/22 13:50
 * @description
 */

/**
 * 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
 * <p>
 * 请你找出并返回只出现一次的那个数。
 * <p>
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,2,3,3,4,4,8,8]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums =  [3,3,7,7,10,11,11]
 * 输出: 10
 */
public class No540 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, 3, 7, 7, 10, 11, 11};
        System.out.println(singleNonDuplicate(nums));
    }

    public static int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 确保mid指向每对元素的第一个
            if (mid % 2 == 1) {
                mid--;
            }

            // 检查mid和mid+1是否相等
            if (nums[mid] == nums[mid + 1]) {
                // 单个元素在右侧
                left = mid + 2;
            } else {
                // 单个元素在左侧（包含mid）
                right = mid;
            }
        }

        return nums[left];
    }

    /**
     * 数组肯定是奇数，数组拆分成三部分 左 中（只有一个数即num[mid]） 右。取 num[mid]跟 num[mid-1]和 num[mid+1]进行比对
     * （1）num[mid] != num[mid-1] 且 num[mid] != num[mid+1] 说明 num[mid] 就是要找的数
     * （2）num[mid] == num[mid-1] ，且 左+中 元素的大小是偶数的话，说明 要找的数在右半部分；不为偶数的话，说明在左半部分
     * （3）num[mid] == num[mid+1]时同理
     * （4）重复上述操作，直到找到该数
     *
     * @param nums
     * @return
     */
    public static int singleNonDuplicate2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 找到中间数的指向索引
            int mid = (left + right) / 2;
            if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
                return nums[mid];
            } else if (nums[mid] == nums[mid - 1]) {
                if ((mid - left + 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                if ((right - mid + 1) % 2 == 0) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
        }

        return nums[left];
    }

    /**
     * 异或符号的用法
     *
     * @param nums
     * @return
     */
    public static int singleNonDuplicate1(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}
